The present invention is generally directed to provisioning circuits in circuit-based communication networks. More specifically, the present invention is directed to provisioning circuits on Multiple Parallel Links between switches in a circuit-based communications network with a single setup message.
Circuit-based communications networks consist of a number of switches (or routers) connected by communication lines. Examples of circuit-based communication networks include optical/electrical switch or optical cross connect networks, ATM networks, frame relay networks, networks of MPLS enabled label switched routers, and networks of Lambda (optical wavelength) routers. In a circuit-based communication network, there can be multiple lines connected between a given pair of switches. These lines can be of various sizes that are generally expressed in bandwidth units, such as OC-48, OC-192, etc. Lines are often grouped (aggregated) into links and certain information is associated with each link. One such piece of information is the administrative weight of the link, which is used in calculating paths for circuits. Another piece of information associated with each link is the physical route or diversity of the link. This information is used to calculate a path with a desired physical route or diversity in mind. For example, it may be desirable that two circuits have physically diverse routes so that a single network failure cannot take down both circuits. Other information associated with each link includes the total bandwidth of the link as well as the available bandwidth on the link. This information is used to find a path for a new circuit that has sufficient bandwidth to accommodate the circuit.
Communication lines connecting switches are grouped into links so that all of the information is not needlessly associated with each line, as many lines have the same physical route and administrative weights. The spare bandwidth on a link is the sum of the spare bandwidths on the lines of the link. When lines have different physical routes and/or administrative weights, it is necessary to group them into multiple parallel links in order to preserve the diversity information. If the lines having different physical routes and/or administrative weights were grouped into one link, the diversity information of the link would be compromised and it would be impossible to satisfy desired diversity requirements of circuits. Many customers demand diverse service routes for many of their circuits. In order to satisfy these diversity requirements, network providers may have many parallel links between pairs of switches.
A circuit-based communication network can be used to connect two end systems by establishing a circuit between the end systems. A circuit between end systems is established by routing between the switches connected to the end systems and can span multiple links. The sequence of links spanned by the circuit is called its (service) route. If there is a failure in the network affecting one or more of the links or switches in the service route of a circuit, then the circuit fails. In this case, the circuit is re-routed on a new (restoration) route that avoids the failed portions of the network. When the failure is repaired, the circuit can revert back to its original service route.
Switches in circuit-based communication networks communicate with each other using routing and signaling protocols in order to automate a variety of functions, such as self-discovery of network resources, construction and maintenance of a link-state database of routing information across all switches, automatic provisioning and restoration of circuits, detection of network failure conditions, and flooding of information related to any change in the state of the network to all switches including failures of switches and links changes in available bandwidth on links, etc. Examples of such routing and signaling protocols include Open Shortest Path First (OSPF), Multi-Protocol label Switching (MPLS), Private Network to Network Interface (PNNI), etc., and variants of these standard protocols that have been adapted to specific networks or applications. Networks using these protocols are characterized by the fact that the intelligence is distributed in every switch and is not centralized. Typically, all switches run the same set of protocols although the functions performed by the switches may vary based on how switches are used. Thus, the switches, while employing the same or similar protocols, operate independently of each other. Any coordination of activities between switches is done by sending messages to each other using the routing and signaling protocols.
In order to provision a new circuit, one switch in the network is selected as a source switch and another switch is selected as a destination switch. The source switch calculates a path for the circuit using information collected by the routing protocol. This information typically includes network topology, available network resources, etc. The path must have sufficient network resources to meet quality of service requirements (bandwidth, delay, etc.) of the circuit. The circuit route is specified as a sequence of links connecting various switches between the source switch and the destination switch. Typically, the path is generated using a variant of Dijkstra's shortest path algorithm, which determines a path with a minimum weight based on weights of the links connecting switches between the source and destination switches.
Once the source switch calculates the path of the circuit, the source switch sets up the circuit using the signaling protocol. The source switch sends a setup message along the selected path of the circuit. Each switch in the path determines whether the requested resources are available and then allocates the resources to the circuit. The setup message contains the selected path, and each switch forwards the setup message to the next switch in the path. If all switches are able to allocate the resources, the setup is successful and the circuit is established. If any switch determines that the requested resources are not available, or cannot allocate the resources for any reason, the setup fails. An unsuccessful setup results in a crankback to the source. A crankback is a message that returns to the source along the same path that the setup message was transmitted and de-allocates the resources previously allocated by the setup message. The crankback message may contain information regarding where the setup failed. The source then calculates a new path for the circuit and sends out a new setup message to setup the new path. The new path must also have sufficient resources to meet the quality of service requirements of the circuit.
When a failure occurs in a circuit-based communication network, such as a fiber cut or switch failure, a number of circuits can fail as a result. The switches adjacent to the location of the failure detect the failure condition, identify the circuits affected by the failure, and generate release messages using the signaling protocol. For each circuit, release messages travel in opposite directions away from the failure to the source and the destination switches of the circuit, releasing all resources allocated to the circuit along the way. The source switch then attempts to restore the circuit by determining a new path and establishing the failed circuit on the new path. The new path must have sufficient network resources to meet the needs of the circuit. The new path must also avoid the failed part of the network. Information about the failed part of the network is disseminated by the routing protocol, but there may be a delay in distributing this information. The release message may also contain information regarding where the circuit failed. In some networks, switches pre-calculate a restoration path for each circuit. This path is attempted first whenever the circuit fails. If the setup attempt on the pre-calculated restoration path fails, then the Dijkstra algorithm is run to obtain a new path.
Unsuccessful restoration attempts result in crankbacks, and in many cases a circuit may crankback multiple times before it is restored. Each crankback increases the amount of time the service associated with the circuit suffers an outage, so it is desirable that the number of crankbacks be minimized. The failed circuits all compete for the same available resources during restoration. In many cases, there are insufficient network resources to restore all of the failed circuits, and some of the circuits cannot be restored until the network failure is fixed.
As described above, switches in a circuit-based communication network communicate using routing and signaling protocol. Whenever the available bandwidth on a link changes, the switches adjacent to that link send out a routing message using the routing protocol to advertise the available bandwidth on the link. This notifies the other switches in the network of the change in available bandwidth on the link. However, in order to keep the number of routing messages in the network in check, a timer is typically used to throttle the number of routing messages. For example, routing messages for a particular link in a network may be sent at a rate no higher than 1 per second.
When a failure occurs, there is a flurry of activity to identify and release the affected circuits and release messages are transmitted using the signaling protocol. These release messages change the available bandwidth of the links the affected circuits traversed. Routing messages are transmitted using the routing protocol to advertise the new available bandwidths. The routing messages are then throttled until the timer controlling them expires. The release messages initiate another more activity as switches attempt to restore the failed circuits for which they are the source. As circuits restore, the available bandwidth on links in the circuit paths changes repeatedly, but these advertising of these changes using the routing protocol is delayed due to the throttling of the routing message. Accordingly, source switches calculate paths for circuits using bandwidth information that may have changed. The setup messages along such paths typically do not succeed resulting in crankbacks and new path calculations. This significantly increases the amount of time required to restore circuits during a network failure.